package 递增子序列;

import java.util.*;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 递增子序列  ,不能排序的去重
 * @date 2022/11/15 15:14
 */
public class Demo491 {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
              backTrack(nums,0);
              return res;
    }

    private void backTrack(int[] nums, int startIndex) {
        if(startIndex>nums.length){
            return;
        }
        if(path.size()>=2&&path.get(path.size()-1)>=path.get(path.size()-2)){
            res.add(new ArrayList(path));
        }
        if(path.size()>=2&&path.get(path.size()-1)<path.get(path.size()-2)){
           return;
        }
        HashSet<Integer> hashSet=new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            //同一层不能重复取值，如果可以排序，可以采用下面方法去重，不能排序则不能用这种方法去重
            if(startIndex<i&&hashSet.contains(nums[i])){
                continue;
            }

            path.add(nums[i]);
            hashSet.add(nums[i]);
            backTrack(nums,i+1);
            path.removeLast();

        }
    }

}

